package com.gitee.wsl.collections.list

import com.gitee.wsl.base.Objects.equals
import com.gitee.wsl.collections.iterator.api.OrderedIterator
import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.lang.character.Ascii

/**
 * A `List` implementation that is optimized for fast insertions and
 * removals at any index in the list.
 *
 *
 * This list implementation utilises a tree structure internally to ensure that
 * all insertions and removals are O(log n). This provides much faster performance
 * than both an `ArrayList` and a `LinkedList` where elements
 * are inserted and removed repeatedly from anywhere in the list.
 *
 *
 *
 * The following relative performance statistics are indicative of this class:
 *
 * <pre>
 * get  add  insert  iterate  remove
 * TreeList       3    5       1       2       1
 * ArrayList      1    1      40       1      40
 * LinkedList  5800    1     350       2     325
</pre> *
 *
 *
 * `ArrayList` is a good general purpose list implementation.
 * It is faster than `TreeList` for most operations except inserting
 * and removing in the middle of the list. `ArrayList` also uses less
 * memory as `TreeList` uses one object per entry.
 *
 *
 *
 * `LinkedList` is rarely a good choice of implementation.
 * `TreeList` is almost always a good replacement for it, although it
 * does use slightly more memory.
 *
 *
 * @param <E> the type of the elements in the list.
 * @since 3.1
</E> */
class TreeList<E> : AbstractMutableList<E> {
    //    add; toArray; iterator; insert; get; indexOf; remove
    //    TreeList = 1260;7360;3080;  160;   170;3400;  170;
    //   ArrayList =  220;1480;1760; 6870;    50;1540; 7200;
    //  LinkedList =  270;7360;3350;55860;290720;2910;55200;
    /**
     * Implements an AVLNode which keeps the offset updated.
     *
     *
     * This node contains the real work.
     * TreeList is just there to implement [java.util.List].
     * The nodes don't know the index of the object they are holding.  They
     * do know however their position relative to their parent node.
     * This allows to calculate the index of a node while traversing the tree.
     *
     *
     * The Faedelung calculation stores a flag for both the left and right child
     * to indicate if they are a child (false) or a link as in linked list (true).
     */
    internal class AVLNode<E> {
        /** The left child node or the predecessor if [.leftIsPrevious]. */
        private var left: AVLNode<E>? = null

        /** Flag indicating that left reference is not a subtree but the predecessor.  */
        private var leftIsPrevious = false

        /** The right child node or the successor if [.rightIsNext].  */
        private var right: AVLNode<E>? = null

        /** Flag indicating that right reference is not a subtree but the successor.  */
        private var rightIsNext = false

        /** How many levels of left/right are below this one.  */
        private var height = 0

        /** The relative position, root holds absolute position.  */
        var relativePosition: Int
        /**
         * Gets the value.
         *
         * @return the value of this node
         */
        /**
         * Sets the value.
         *
         * @param obj  the value to store
         */
        /** The stored element.  */
        var value: E?

        /**
         * Constructs a new AVL tree from a collection.
         *
         *
         * The collection must be nonempty.
         *
         * @param coll  a nonempty collection
         */
        constructor(coll: Collection<E>) : this(coll.iterator(), 0, coll.size - 1, 0, null, null)

        /**
         * Constructs a new node with a relative position.
         *
         * @param relativePosition  the relative position of the node
         * @param obj  the value for the node
         * @param rightFollower the node with the value following this one
         * @param leftFollower the node with the value leading this one
         */
        constructor(
            relativePosition: Int, 
            obj: E?,
            rightFollower: AVLNode<E>?, leftFollower: AVLNode<E>?,
        ) {
            this.relativePosition = relativePosition
            value = obj
            rightIsNext = true
            leftIsPrevious = true
            right = rightFollower
            left = leftFollower
        }

        /**
         * Constructs a new AVL tree from a collection.
         *
         *
         * This is a recursive helper for [.AVLNode]. A call
         * to this method will construct the subtree for elements `start`
         * through `end` of the collection, assuming the iterator
         * `e` already points at element `start`.
         *
         * @param iterator  an iterator over the collection, which should already point
         * to the element at index `start` within the collection
         * @param start  the index of the first element in the collection that
         * should be in this subtree
         * @param end  the index of the last element in the collection that
         * should be in this subtree
         * @param absolutePositionOfParent  absolute position of this node's
         * parent, or 0 if this node is the root
         * @param prev  the `AVLNode` corresponding to element (start - 1)
         * of the collection, or null if start is 0
         * @param next  the `AVLNode` corresponding to element (end + 1)
         * of the collection, or null if end is the last element of the collection
         */
        private constructor(
            iterator: Iterator<E>, start: Int, end: Int,
            absolutePositionOfParent: Int, prev: AVLNode<E>?, next: AVLNode<E>?,
        ) {
            val mid = start + (end - start) / 2
            if (start < mid) {
                left = TreeList.AVLNode(iterator, start, mid - 1, mid, prev, this)
            } else {
                leftIsPrevious = true
                left = prev
            }
            value = iterator.next()
            relativePosition = mid - absolutePositionOfParent
            if (mid < end) {
                right = TreeList.AVLNode(iterator, mid + 1, end, mid, this, next)
            } else {
                rightIsNext = true
                right = next
            }
            recalcHeight()
        }

        /**
         * Appends the elements of another tree list to this tree list by efficiently
         * merging the two AVL trees. This operation is destructive to both trees and
         * runs in O(log(m + n)) time.
         *
         * @param otherTree
         * the root of the AVL tree to merge with this one
         * @param currentSize
         * the number of elements in this AVL tree
         * @return the root of the new, merged AVL tree
         */
        fun addAll(otherTree: AVLNode<E>, currentSize: Int): AVLNode<E>? {
            var otherTree:AVLNode<E>? = otherTree
            val maxNode = max()
            val otherTreeMin = otherTree!!.min()

            // We need to efficiently merge the two AVL trees while keeping them
            // balanced (or nearly balanced). To do this, we take the shorter
            // tree and combine it with a similar-height subtree of the taller
            // tree. There are two symmetric cases:
            //   * this tree is taller, or
            //   * otherTree is taller.
            if (otherTree.height > height) {
                // CASE 1: The other tree is taller than this one. We will thus
                // merge this tree into otherTree.

                // STEP 1: Remove the maximum element from this tree.

                val leftSubTree = removeMax()

                // STEP 2: Navigate left from the root of otherTree until we
                // find a subtree, s, that is no taller than me. (While we are
                // navigating left, we store the nodes we encounter in a stack
                // so that we can re-balance them in step 4.)
                val sAncestors = ArrayDeque<AVLNode<E>>()
                var s: AVLNode<E>? = otherTree
                var sAbsolutePosition = s!!.relativePosition + currentSize
                var sParentAbsolutePosition = 0
                while (s != null && s.height > getHeight(leftSubTree)) {
                    sParentAbsolutePosition = sAbsolutePosition
                    sAncestors.push(s)
                    s = s.left
                    if (s != null) {
                        sAbsolutePosition += s.relativePosition
                    }
                }

                // STEP 3: Replace s with a newly constructed subtree whose root
                // is maxNode, whose left subtree is leftSubTree, and whose right
                // subtree is s.
                maxNode.setLeft(leftSubTree, null)
                maxNode.setRight(s, otherTreeMin)
                if (leftSubTree != null) {
                    leftSubTree.max().setRight(null, maxNode)
                    leftSubTree.relativePosition -= currentSize - 1
                }
                if (s != null) {
                    s.min().setLeft(null, maxNode)
                    s.relativePosition = sAbsolutePosition - currentSize + 1
                }
                maxNode.relativePosition = currentSize - 1 - sParentAbsolutePosition
                otherTree.relativePosition += currentSize

                // STEP 4: Re-balance the tree and recalculate the heights of s's ancestors.
                s = maxNode
                while (!sAncestors.isEmpty()) {
                    val sAncestor = sAncestors.pop()
                    sAncestor.setLeft(s, null)
                    s = sAncestor.balance()
                }
                return s
            }
            otherTree = otherTree.removeMin()

            val sAncestors = ArrayDeque<AVLNode<E>>()
            var s: AVLNode<E>? = this
            var sAbsolutePosition = s!!.relativePosition
            var sParentAbsolutePosition = 0
            while (s != null && s.height > getHeight(otherTree)) {
                sParentAbsolutePosition = sAbsolutePosition
                sAncestors.push(s)
                s = s.right
                if (s != null) {
                    sAbsolutePosition += s.relativePosition
                }
            }

            otherTreeMin.setRight(otherTree, null)
            otherTreeMin.setLeft(s, maxNode)
            if (otherTree != null) {
                otherTree.min().setLeft(null, otherTreeMin)
                otherTree.relativePosition++
            }
            if (s != null) {
                s.max().setRight(null, otherTreeMin)
                s.relativePosition = sAbsolutePosition - currentSize
            }
            otherTreeMin.relativePosition = currentSize - sParentAbsolutePosition

            s = otherTreeMin
            while (!sAncestors.isEmpty()) {
                val sAncestor = sAncestors.pop()
                sAncestor!!.setRight(s, null)
                s = sAncestor.balance()
            }
            return s
        }

        /**
         * Balances according to the AVL algorithm.
         */
        private fun balance(): AVLNode<E> {
            when (heightRightMinusLeft()) {
                1, 0, -1 -> return this
                -2 -> {
                    if (left!!.heightRightMinusLeft() > 0) {
                        setLeft(left!!.rotateLeft(), null)
                    }
                    return rotateRight()
                }

                2 -> {
                    if (right!!.heightRightMinusLeft() < 0) {
                        setRight(right!!.rotateRight(), null)
                    }
                    return rotateLeft()
                }

                else -> throw IllegalStateException("tree inconsistent!")
            }
        }

        /**
         * Locate the element with the given index relative to the
         * offset of the parent of this node.
         */
        fun get(index: Int): AVLNode<E>? {
            val indexRelativeToMe = index - relativePosition

            if (indexRelativeToMe == 0) {
                return this
            }

            val nextNode = if (indexRelativeToMe < 0) this.leftSubTree else this.rightSubTree
            if (nextNode == null) {
                return null
            }
            return nextNode.get(indexRelativeToMe)
        }

        /**
         * Returns the height of the node or -1 if the node is null.
         */
        private fun getHeight(node: AVLNode<E>?): Int {
            return if (node == null) -1 else node.height
        }

        private val leftSubTree: AVLNode<E>?
            /**
             * Gets the left node, returning null if it's a faedelung.
             */
            get() = if (leftIsPrevious) null else left

        /**
         * Gets the relative position.
         */
        private fun getOffset(node: AVLNode<E>?): Int {
            if (node == null) {
                return 0
            }
            return node.relativePosition
        }

        private val rightSubTree: AVLNode<E>?
            /**
             * Gets the right node, returning null if it's a faedelung.
             */
            get() = if (rightIsNext) null else right

        /**
         * Returns the height difference right - left
         */
        private fun heightRightMinusLeft(): Int {
            return getHeight(this.rightSubTree) - getHeight(this.leftSubTree)
        }

        /**
         * Locate the index that contains the specified object.
         */
        fun indexOf(`object`: E, index: Int): Int {
            if (this.leftSubTree != null) {
                val result = left!!.indexOf(`object`, index + left!!.relativePosition)
                if (result != -1) {
                    return result
                }
            }
            if (equals(value, `object`)) {
                return index
            }
            if (this.rightSubTree != null) {
                return right!!.indexOf(`object`, index + right!!.relativePosition)
            }
            return -1
        }

        /**
         * Inserts a node at the position index.
         *
         * @param index is the index of the position relative to the position of
         * the parent node.
         * @param obj is the object to be stored in the position.
         */
        fun insert(index: Int, obj: E?): AVLNode<E> {
            val indexRelativeToMe = index - relativePosition

            if (indexRelativeToMe <= 0) {
                return insertOnLeft(indexRelativeToMe, obj)
            }
            return insertOnRight(indexRelativeToMe, obj)
        }

        private fun insertOnLeft(indexRelativeToMe: Int, obj: E?): AVLNode<E> {
            if (this.leftSubTree == null) {
                setLeft(TreeList.AVLNode<E>(-1, obj, this, left), null)
            } else {
                setLeft(left!!.insert(indexRelativeToMe, obj), null)
            }

            if (relativePosition >= 0) {
                relativePosition++
            }
            val ret = balance()
            recalcHeight()
            return ret
        }

        private fun insertOnRight(indexRelativeToMe: Int, obj: E?): AVLNode<E> {
            if (this.rightSubTree == null) {
                setRight(TreeList.AVLNode<E>(+1, obj, right, this), null)
            } else {
                setRight(right!!.insert(indexRelativeToMe, obj), null)
            }
            if (relativePosition < 0) {
                relativePosition--
            }
            val ret = balance()
            recalcHeight()
            return ret
        }

        /**
         * Gets the rightmost child of this node.
         *
         * @return the rightmost child (greatest index)
         */
        private fun max(): AVLNode<E> {
            return if (this.rightSubTree == null) this else right!!.max()
        }

        /**
         * Gets the leftmost child of this node.
         *
         * @return the leftmost child (smallest index)
         */
        private fun min(): AVLNode<E> {
            return if (this.leftSubTree == null) this else left!!.min()
        }

        /**
         * Gets the next node in the list after this one.
         *
         * @return the next node
         */
        fun next(): AVLNode<E>? {
            if (rightIsNext || right == null) {
                return right
            }
            return right!!.min()
        }

        /**
         * Gets the node in the list before this one.
         *
         * @return the previous node
         */
        fun previous(): AVLNode<E>? {
            if (leftIsPrevious || left == null) {
                return left
            }
            return left!!.max()
        }

        /**
         * Sets the height by calculation.
         */
        private fun recalcHeight() {
            height = kotlin.math.max(
                if (this.leftSubTree == null) -1 else this.leftSubTree!!.height,
                if (this.rightSubTree == null) -1 else this.rightSubTree!!.height
            ) + 1
        }

        /**
         * Removes the node at a given position.
         *
         * @param index is the index of the element to be removed relative to the position of
         * the parent node of the current node.
         */
        fun remove(index: Int): AVLNode<E>? {
            val indexRelativeToMe = index - relativePosition

            if (indexRelativeToMe == 0) {
                return removeSelf()
            }
            if (indexRelativeToMe > 0) {
                setRight(right!!.remove(indexRelativeToMe), right!!.right)
                if (relativePosition < 0) {
                    relativePosition++
                }
            } else {
                setLeft(left!!.remove(indexRelativeToMe), left!!.left)
                if (relativePosition > 0) {
                    relativePosition--
                }
            }
            recalcHeight()
            return balance()
        }

        private fun removeMax(): AVLNode<E>? {
            if (this.rightSubTree == null) {
                return removeSelf()
            }
            setRight(right!!.removeMax(), right!!.right)
            if (relativePosition < 0) {
                relativePosition++
            }
            recalcHeight()
            return balance()
        }

        private fun removeMin(): AVLNode<E>? {
            if (this.leftSubTree == null) {
                return removeSelf()
            }
            setLeft(left!!.removeMin(), left!!.left)
            if (relativePosition > 0) {
                relativePosition--
            }
            recalcHeight()
            return balance()
        }

        /**
         * Removes this node from the tree.
         *
         * @return the node that replaces this one in the parent
         */
        private fun removeSelf(): AVLNode<E>? {
            if (this.rightSubTree == null && this.leftSubTree == null) {
                return null
            }
            if (this.rightSubTree == null) {
                if (relativePosition > 0) {
                    left!!.relativePosition += relativePosition
                }
                left!!.max().setRight(null, right)
                return left
            }
            if (this.leftSubTree == null) {
                right!!.relativePosition += relativePosition - (if (relativePosition < 0) 0 else 1)
                right!!.min().setLeft(null, left)
                return right
            }

            if (heightRightMinusLeft() > 0) {
                // more on the right, so delete from the right
                val rightMin = right!!.min()
                value = rightMin.value
                if (leftIsPrevious) {
                    left = rightMin.left
                }
                right = right!!.removeMin()
                if (relativePosition < 0) {
                    relativePosition++
                }
            } else {
                // more on the left or equal, so delete from the left
                val leftMax = left!!.max()
                value = leftMax.value
                if (rightIsNext) {
                    right = leftMax.right
                }
                val leftPrevious = left!!.left
                left = left!!.removeMax()
                if (left == null) {
                    // special case where left that was deleted was a double link
                    // only occurs when height difference is equal
                    left = leftPrevious
                    leftIsPrevious = true
                }
                if (relativePosition > 0) {
                    relativePosition--
                }
            }
            recalcHeight()
            return this
        }

        private fun rotateLeft(): AVLNode<E> {
            val newTop = right // can't be faedelung!
            val movedNode = this.rightSubTree!!.leftSubTree

            val newTopPosition = relativePosition + getOffset(newTop)
            val myNewPosition = -newTop!!.relativePosition
            val movedPosition = getOffset(newTop) + getOffset(movedNode)

            setRight(movedNode, newTop)
            newTop.setLeft(this, null)

            setOffset(newTop, newTopPosition)
            setOffset(this, myNewPosition)
            setOffset(movedNode, movedPosition)
            return newTop
        }

        private fun rotateRight(): AVLNode<E> {
            val newTop = left // can't be faedelung
            val movedNode = this.leftSubTree!!.rightSubTree

            val newTopPosition = relativePosition + getOffset(newTop)
            val myNewPosition = -newTop!!.relativePosition
            val movedPosition = getOffset(newTop) + getOffset(movedNode)

            setLeft(movedNode, newTop)
            newTop.setRight(this, null)

            setOffset(newTop, newTopPosition)
            setOffset(this, myNewPosition)
            setOffset(movedNode, movedPosition)
            return newTop
        }

        /**
         * Sets the left field to the node, or the previous node if that is null
         *
         * @param node  the new left subtree node
         * @param previous  the previous node in the linked list
         */
        private fun setLeft(node: AVLNode<E>?, previous: AVLNode<E>?) {
            leftIsPrevious = node == null
            left = if (leftIsPrevious) previous else node
            recalcHeight()
        }

        /**
         * Sets the relative position.
         */
        private fun setOffset(node: AVLNode<E>?, newOffset: Int): Int {
            if (node == null) {
                return 0
            }
            val oldOffset = getOffset(node)
            node.relativePosition = newOffset
            return oldOffset
        }

        /**
         * Sets the right field to the node, or the next node if that is null
         *
         * @param node  the new left subtree node
         * @param next  the next node in the linked list
         */
        private fun setRight(node: AVLNode<E>?, next: AVLNode<E>?) {
            rightIsNext = node == null
            right = if (rightIsNext) next else node
            recalcHeight()
        }

        /**
         * Stores the node and its children into the array specified.
         *
         * @param array the array to be filled
         * @param index the index of this node
         */
        fun toArray(array: Array<Any?>, index: Int) {
            array[index] = value
            if (this.leftSubTree != null) {
                left!!.toArray(array, index + left!!.relativePosition)
            }
            if (this.rightSubTree != null) {
                right!!.toArray(array, index + right!!.relativePosition)
            }
        }

        //      private void checkFaedelung() {
        //          AVLNode maxNode = left.max();
        //          if (!maxNode.rightIsFaedelung || maxNode.right != this) {
        //              throw new RuntimeException(maxNode + " should right-faedel to " + this);
        //          }
        //          AVLNode minNode = right.min();
        //          if (!minNode.leftIsFaedelung || minNode.left != this) {
        //              throw new RuntimeException(maxNode + " should left-faedel to " + this);
        //          }
        //      }
        //
        //        private int checkTreeDepth() {
        //            int hright = (getRightSubTree() == null ? -1 : getRightSubTree().checkTreeDepth());
        //            //          System.out.print("checkTreeDepth");
        //            //          System.out.print(this);
        //            //          System.out.print(" left: ");
        //            //          System.out.print(_left);
        //            //          System.out.print(" right: ");
        //            //          System.out.println(_right);
        //
        //            int hleft = (left == null ? -1 : left.checkTreeDepth());
        //            if (height != Math.max(hright, hleft) + 1) {
        //                throw new RuntimeException(
        //                    "height should be max" + hleft + "," + hright + " but is " + height);
        //            }
        //            return height;
        //        }
        //
        //        private int checkLeftSubNode() {
        //            if (getLeftSubTree() == null) {
        //                return 0;
        //            }
        //            int count = 1 + left.checkRightSubNode();
        //            if (left.relativePosition != -count) {
        //                throw new RuntimeException();
        //            }
        //            return count + left.checkLeftSubNode();
        //        }
        //
        //        private int checkRightSubNode() {
        //            AVLNode right = getRightSubTree();
        //            if (right == null) {
        //                return 0;
        //            }
        //            int count = 1;
        //            count += right.checkLeftSubNode();
        //            if (right.relativePosition != count) {
        //                throw new RuntimeException();
        //            }
        //            return count + right.checkRightSubNode();
        //        }
        /**
         * Used for debugging.
         */
        override fun toString(): String {
            return StringBuilder()
                .append("AVLNode(")
                .append(relativePosition)
                .append(Ascii.COMMA)
                .append(left != null)
                .append(Ascii.COMMA)
                .append(value)
                .append(Ascii.COMMA)
                .append(this.rightSubTree != null)
                .append(rightIsNext)
                .append(")")
                .toString()
        }
    }

    /**
     * A list iterator over the linked list.
     */
    internal class TreeListIterator<E>(
        /** The parent list  */
        private val parent: TreeList<E>,
        /**
         * The index of the next node to be returned.
         */
        private var nextIndex: Int,
    ) : MutableListIterator<E>, OrderedIterator<E> {
        /**
         * Cache of the next node that will be returned by [.next].
         */
        private var next: AVLNode<E>?

        /**
         * Cache of the last node that was returned by [.next]
         * or [.previous].
         */
        private var current: AVLNode<E>? = null

        /**
         * The index of the last node that was returned.
         */
        private var currentIndex: Int

        /**
         * The modification count that the list is expected to have. If the list
         * doesn't have this count, then a
         * [ConcurrentModificationException] may be thrown by
         * the operations.
         */
        private var expectedModCount: Int = parent.modCount

        /**
         * Create a ListIterator for a list.
         *
         * @param parent  the parent list
         * @param nextIndex  the index to start at
         */
        init {
            this.next = if (parent.root == null) null else parent.root!!.get(nextIndex)
            this.currentIndex = -1
        }

         override fun add(element: E) {
            checkModCount()
            parent.add(nextIndex, element)
            current = null
            currentIndex = -1
            nextIndex++
            expectedModCount++
        }

        /**
         * Checks the modification count of the list is the value that this
         * object expects.
         *
         * @throws ConcurrentModificationException If the list's modification
         * count isn't the value that was expected.
         */
        protected fun checkModCount() {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
        }

         override fun hasNext(): Boolean {
            return nextIndex < parent.size
        }

        override fun hasPrevious(): Boolean {
            return nextIndex > 0
        }

         override fun next(): E {
            checkModCount()
            if (!hasNext()) {
                throw NoSuchElementException("No element at index $nextIndex.")
            }
            if (next == null) {
                next = parent.root!!.get(nextIndex)
            }
            val value = next!!.value
            current = next
            currentIndex = nextIndex++
            next = next!!.next()
            return value!!
        }

         override fun nextIndex(): Int {
            return nextIndex
        }

        override fun previous(): E {
            checkModCount()
            if (!hasPrevious()) {
                throw NoSuchElementException("Already at start of list.")
            }
            if (next == null) {
                next = parent.root!!.get(nextIndex - 1)
            } else {
                next = next!!.previous()
            }
            val value = next!!.value
            current = next
            currentIndex = --nextIndex
            return value!!
        }

         override fun previousIndex(): Int {
            return nextIndex() - 1
        }

         override fun remove() {
            checkModCount()
            check(currentIndex != -1)
            parent.removeAt(currentIndex)
            if (nextIndex != currentIndex) {
                // remove() following next()
                nextIndex--
            }
            // the AVL node referenced by next may have become stale after a remove
            // reset it now: will be retrieved by next call to next()/previous() via nextIndex
            next = null
            current = null
            currentIndex = -1
            expectedModCount++
        }

         override fun set(element: E) {
            checkModCount()
            checkNotNull(current)
            current!!.value = element
        }
    }

    /** The root node in the AVL tree  */
    private var root: AVLNode<E>? = null

    /** The current size of the list  */
    override var size = 0

    /**
     * Constructs a new empty list.
     */
    constructor()

    /**
     * Constructs a new empty list that copies the specified collection.
     *
     * @param coll  the collection to copy
     * @throws NullPointerException if the collection is null
     */
    constructor(coll: Collection<E>) {
        if (!coll.isEmpty()) {
            root = TreeList.AVLNode(coll)
            size = coll.size
        }
    }

    /**
     * Adds a new element to the list.
     *
     * @param index  the index to add before
     * @param element  the element to add
     */
     override fun add(index: Int, element: E) {
        modCount++
        checkInterval(index, 0, size)
        if (root == null) {
            root = TreeList.AVLNode(index, element, null, null)
        } else {
            root = root!!.insert(index, element)
        }
        size++
    }

    /**
     * Appends all the elements in the specified collection to the end of this list,
     * in the order that they are returned by the specified collection's Iterator.
     *
     *
     * This method runs in O(n + log m) time, where m is
     * the size of this list and n is the size of `c`.
     *
     * @param c  the collection to be added to this list
     * @return `true` if this list changed as a result of the call
     * @throws NullPointerException if the specified collection contains a
     * null element and this collection does not permit null elements,
     * or if the specified collection is null
     */
     override fun addAll(c: Collection<E>): Boolean {
        if (c.isEmpty()) {
            return false
        }
        modCount += c.size
        val cTree = TreeList.AVLNode(c)
        root = if (root == null) cTree else root!!.addAll(cTree, size)
        size += c.size
        return true
    }

    /**
     * Checks whether the index is valid.
     *
     * @param index  the index to check
     * @param startIndex  the first allowed index
     * @param endIndex  the last allowed index
     * @throws IndexOutOfBoundsException if the index is invalid
     */
    private fun checkInterval(index: Int, startIndex: Int, endIndex: Int) {
        if (index < startIndex || index > endIndex) {
            throw IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size)
        }
    }

    /**
     * Clears the list, removing all entries.
     */
     override fun clear() {
        modCount++
        root = null
        size = 0
    }

    /**
     * Searches for the presence of an object in the list.
     *
     * @param element  the object to check
     * @return true if the object is found
     */
     override fun contains(element: E): Boolean {
        return indexOf(element) >= 0
    }

    /**
     * Gets the element at the specified index.
     *
     * @param index  the index to retrieve
     * @return the element at the specified index
     */
     override fun get(index: Int): E {
        checkInterval(index, 0, size - 1)
        return root!!.get(index)!!.value!!
    }

    /**
     * Searches for the index of an object in the list.
     *
     * @param element  the object to search
     * @return the index of the object, -1 if not found
     */
     override fun indexOf(element: E): Int {
        // override to go 75% faster
        if (root == null) {
            return -1
        }
        return root!!.indexOf(element, root!!.relativePosition)
    }

    /**
     * Gets an iterator over the list.
     *
     * @return an iterator over the list
     */
     override fun iterator(): MutableIterator<E> {
        // override to go 75% faster
        return listIterator(0)
    }

    /**
     * Gets a ListIterator over the list.
     *
     * @return the new iterator
     */
     override fun listIterator(): MutableListIterator<E> {
        // override to go 75% faster
        return listIterator(0)
    }

    /**
     * Gets a ListIterator over the list.
     *
     * @param index  the index to start from
     * @return the new iterator
     */
     override fun listIterator(index: Int): MutableListIterator<E> {
        // override to go 75% faster
        // cannot use EmptyIterator as iterator.add() must work
        checkInterval(index, 0, size)
        return TreeList.TreeListIterator(this, index)
    }

    /**
     * Removes the element at the specified index.
     *
     * @param index  the index to remove
     * @return the previous object at that index
     */
     override fun removeAt(index: Int): E {
        modCount++
        checkInterval(index, 0, size - 1)
        val result = get(index)
        root = root!!.remove(index)
        size--
        return result!!
    }

    /**
     * Sets the element at the specified index.
     *
     * @param index  the index to set
     * @param element  the object to store at the specified index
     * @return the previous object at that index
     * @throws IndexOutOfBoundsException if the index is invalid
     */
     override fun set(index: Int, element: E): E {
        checkInterval(index, 0, size - 1)
        val node = root!!.get(index)
        val result = node!!.value
        node.value = element
        return result!!
    }

    /**
     * Gets the current size of the list.
     *
     * @return the current size
     */
//     override fun size: Int {
//        return size
//    }

    /**
     * Converts the list into an array.
     *
     * @return the list as an array
     */
//      fun toArray(): Array<Any?> {
//        // override to go 20% faster
//        val array = kotlin.arrayOfNulls<Any>(size)
//        if (root != null) {
//            root!!.toArray(array, root!!.relativePosition)
//        }
//        return array
//    }
}

fun <E> treeListOf(vararg elements: E): TreeList<E> {
    val list = TreeList<E>()
    if(elements.isNotEmpty())
        list.addAll(elements.toList())
    return list
}

fun <E> treeListOf(elements: Iterable<E>): TreeList<E> {
    val list = TreeList<E>()
    list.addAll(elements)
    return list
}
